﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace Acoris.Foundation
{
    /// <summary>
    /// 表示一个双端队列
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class Deque<T>:ICollection<T>
    {
        #region Fields

        T[] m_array = Arrays<T>.EmptyArray;
        int m_capacity;
        int m_count;
        int m_tail;
        int m_head;

        #endregion

        #region Constructor

        public Deque() { }

        public Deque(int capacity)
        {
            m_capacity = capacity;
            m_array = new T[m_capacity];
            m_count = m_head = m_tail = 0;
        }

        #endregion

        //  head                                    tail
        //  ---------------------------------------------
        //  |   |   |   |   |   |   |   |   |   |   |   |
        //  ---------------------------------------------
        //  head ---->
        //                                     <---- tail

        /// <summary>
        /// 将指定元素插入当前队列末端
        /// </summary>
        /// <param name="item">指定要插入的元素</param>
        public void PushBack(T item)
        {
            EnsureCapacity();

            if (m_tail == 0) {
                m_tail = m_capacity - 1;
            }
            m_array[m_tail--] = item;
            m_count++;
        }

        /// <summary>
        /// 获取当前队列末端的元素
        /// </summary>
        /// <returns>返回当前队列末端的元素</returns>
        public T PopBack()
        {
            if (Count == 0) {
                throw new InvalidOperationException("队列为空");
            }

            if (m_tail == m_capacity - 1) {
                m_tail = 0;
            }
            else {
                m_tail--;
            }

            var element = m_array[m_tail];
            m_count--;
            return element;

        }

        /// <summary>
        /// 将指定元素插入当前队列前端
        /// </summary>
        /// <param name="item">指定要插入的对象</param>
        public void PushFront(T item)
        {
            EnsureCapacity();

            if (m_head == m_capacity - 1) {
                m_head = 0;
            }
            m_array[m_head++] = item;
        }

        /// <summary>
        /// 获取当前队列前端位置的元素
        /// </summary>
        /// <returns>返回当前队列前端位置的元素</returns>
        public T PopFront()
        {
            if(m_count == 0) {
                throw new InvalidOperationException("队列为空");
            }

            if(m_head == 0) {
                m_head = m_capacity - 1;
            }
            else {
                m_head--;
            }

            var element = m_array[m_head];
            m_count--;
            return element;
        }

        void EnsureCapacity()
        {
            if (m_capacity == m_count || m_tail == m_head) {
                var newCapacity = m_capacity *2;
                var oldArray = m_array;
                m_array = new T[newCapacity];
                m_capacity = newCapacity;
                m_tail += (newCapacity - oldArray.Length);
                CopyTo(oldArray, m_array, 0);
            }
        }

        public void CopyTo(T[] array,int arrayIndex)
        {
            if(array.Length < m_array.Length + arrayIndex) {
                throw new ArgumentOutOfRangeException("数组长度不足");
            }

            Array.Copy(m_array, 0, array, arrayIndex, m_head);
            Array.Copy(m_array, m_tail, array, arrayIndex + m_tail, m_array.Length - m_tail - 1);
        }

        void CopyTo(T[] m_array, T[] array,int arrayIndex)
        {
            if (array.Length < m_array.Length + arrayIndex) {
                throw new ArgumentOutOfRangeException("数组长度不足");
            }

            Array.Copy(m_array, 0, array, arrayIndex, m_head);
            Array.Copy(m_array, m_tail + 1, array, arrayIndex + m_tail, m_array.Length - m_tail);
        }

        /// <summary>
        /// 返回当前集合中元素的个数
        /// </summary>
        public int Count {
            get { return m_count; }
        }

        /// <summary>
        /// 返回当前集合的容量
        /// </summary>
        public int Capacity {
            get { return m_capacity; }
        }

        /// <summary>
        /// 获取一个值，该值指示当前集合是否只读
        /// </summary>
        public bool IsReadOnly {
            get { return false; }
        }

        /// <summary>
        /// 获取与当前对象等价的字符串形式
        /// </summary>
        /// <returns>返回与当前对象等价的字符串形式</returns>
        public override string ToString()
        {
            return m_count == 0 ? "empty" : $"count:{m_count}";
        }

        public void Add(T item)
        {
            PushFront(item);
        }

        public void Clear()
        {
            Array.Clear(m_array, 0, m_array.Length);
            m_count = 0;
            m_head = m_tail = 0;
        }

        public bool Contains(T item)
        {
            throw new NotSupportedException();
        }

        public bool Remove(T item)
        {
            throw new NotSupportedException();
        }

        public T Tail {
            get {
                if(m_count == 0) {
                    return default(T);
                }
                else {
                    return m_array[m_tail + 1];
                }
            }
        }

        public T Front {
            get {
                if (m_count == 0) {
                    return default(T);
                }
                else {
                    return m_array[m_head - 1];
                }
            }
        }

        public IEnumerator<T> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            throw new NotImplementedException();
        }
    }
}
